package Hot_100;//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

/*
    思路：按照插入排序的思想来写
* */
public class T21_mergeTwoLists {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(4);
        l1.next = l2;
        l2.next = l3;
        l3.next = null;

        ListNode l4 = new ListNode(1);
        ListNode l5 = new ListNode(3);
        ListNode l6 = new ListNode(4);
        l4.next = l5;
        l5.next = l6;
        l6.next = null;


        ListNode listNode = mergeTwoLists_2(l1, l4);
        while (listNode != null) {
            System.out.print(listNode.val+" ");
            listNode = listNode.next;
        }
    }

//    直接合并
    public static ListNode mergeTwoLists_2(ListNode l1, ListNode l2) {
        // 类似归并排序中的合并过程
        ListNode dummyHead = new ListNode();  //dummyHead 是头结点,下一个结点才是首结点
        ListNode cur = dummyHead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {  //cur充当前驱,l1和l2是后继
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            } else {
                cur.next = l2;
                cur = cur.next;
                l2 = l2.next;
            }
        }
        // 任一为空，直接连接另一条链表
        if (l1 == null) {
            cur.next = l2;
        } else {
            cur.next = l1;
        }
        return dummyHead.next;
    }


//    递归
    public static ListNode mergeTwoLists_1(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }

        if (list1.val < list2.val) {    //找出较小值结点list1作为前驱，list1的后面部分和list2作为后继，递归下去，最后得到结果
            list1.next = mergeTwoLists_1(list1.next, list2);
            return list1;
        }else { //找出较小值结点list2作为前驱，list2的后面部分和list1作为后继
            list2.next = mergeTwoLists_1(list1, list2.next);
            return list2;
        }
    }
}